package oct2013.linkednode;

public class RecoverBinarySearchTree {
	TreeNode prev;
	TreeNode node1, node2;

	public void recoverTree(TreeNode root) {
		prev = null;
		node1 = null;
		node2 = null;
		preorder(root);
		int tmp = node1.val;
		node1.val = node2.val;
		node2.val = tmp;
	}

	void preorder(TreeNode root) {
		if (root == null)
			return;
		preorder(root.left);
		if (prev != null && prev.val > root.val && node1 == null) {
			node1 = prev;
		}
		if (prev != null && root.val < prev.val) {
			node2 = root;
		}
		prev = root;
		preorder(root.right);
	}
}
